class Solution:
    _MOD = 10 ** 9 + 7

    def checkRecord(self, n: int) -> int:
        # 计算没有A的情况
        dp1 = [[0, 0, 0] for _ in range(n + 1)]
        dp1[0][0] = 1
        dp1[1][0] = 1
        dp1[1][1] = 1
        for i in range(2, n + 1):
            dp1[i][0] = (dp1[i - 1][0] + dp1[i - 1][1] + dp1[i - 1][2]) % self._MOD
            dp1[i][1] = dp1[i - 1][0]
            dp1[i][2] = dp1[i - 1][1]

        dp2 = [0] * (n + 1)
        for i in range(n + 1):
            dp2[i] = (dp1[i][0] + dp1[i][1] + dp1[i][2]) % self._MOD

        # 选择A的位置
        ans = dp2[n]
        for i in range(n):
            ans += (dp2[i] * dp2[n - i - 1]) % self._MOD
        return ans % self._MOD


if __name__ == "__main__":
    print(Solution().checkRecord(2))  # 8
